package zhoug.map;

import zhoug.map.location.ILatLng;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * 数据抽稀算法
 * 道格拉斯-普克算法
 * @Author: zhoug
 * @Date: 2025-01-02
 * @Description: 未完成
 */
public class DouglasPeucker {
    private static double epsilon = 40; // 距离阈值

    public static  <T extends ILatLng> List<T> simplify(List<T> points) {
        if (points.size() < 3) {
            return points;
        }
        // 获取起始和结束点
        int firstIndex = 0;
        int lastIndex = points.size() - 1;
        // 记录要保留的点
        List<Integer> pointIndexsToKeep = new ArrayList<>();
        pointIndexsToKeep.add(firstIndex);
        pointIndexsToKeep.add(lastIndex);
        // 递归简化
        reduce(points, firstIndex, lastIndex, pointIndexsToKeep);
        // 根据保留的点生成新的简化后的列表
        List<T> result = new ArrayList<>();
        for (int index : pointIndexsToKeep) {
            result.add(points.get(index));
        }
        return result;
    }

    private static <T extends ILatLng> void reduce(List<T> points, int firstIndex, int lastIndex, List<Integer> pointIndexsToKeep) {
        double maxDistance = 0;
        int indexFarthest = 0;
        // 遍历寻找最大距离
        List<Double> dis=new ArrayList<>();
        for (int index = firstIndex + 1; index < lastIndex; index++) {
            double distance = perpendicularDistance(points.get(firstIndex), points.get(lastIndex), points.get(index));
            dis.add(distance);
            if (distance > maxDistance) {
                maxDistance = distance;
                indexFarthest = index;
            }
        }
        Collections.sort(dis);

        // 如果最大距离超过阈值，保留该点
        if (maxDistance > epsilon) {
            pointIndexsToKeep.add(indexFarthest);
            // 递归执行
            reduce(points, firstIndex, indexFarthest, pointIndexsToKeep);
            reduce(points, indexFarthest, lastIndex, pointIndexsToKeep);
        }

    }
    private static double perpendicularDistance(ILatLng start, ILatLng end, ILatLng point) {
        // 计算点到线的垂直距离
        double area = Math.abs((start.getLatitude() * end.getLongitude() + end.getLatitude() * point.getLongitude() + point.getLatitude() * start.getLongitude())
                - (end.getLatitude() * start.getLongitude() + point.getLatitude() * end.getLongitude() + start.getLatitude() * point.getLongitude()));
        double bottom = Math.sqrt(Math.pow(start.getLatitude() - end.getLatitude(), 2) + Math.pow(start.getLongitude() - end.getLongitude(), 2));
        return area / bottom * 2;
    }



    public static <T extends ILatLng> List<T> reduceMarkers(List<T> allMarkers, int count, double tolerance){
        if(allMarkers.size()<=count){
            return allMarkers;
        }
        return reduceMarkers(allMarkers, tolerance);
    }

    public static <T extends ILatLng>  List<T> reduceMarkers(List<T> allMarkers, double tolerance) {
        List<T> resultMarkers = new ArrayList<>();
        if (allMarkers.isEmpty()) {
            return resultMarkers;
        }
        // 复制原始标记点
        List<T> markers = new ArrayList<>(allMarkers);
        // 初始化第一个点
        T last = markers.remove(0);
        resultMarkers.add(last);
        Iterator<T> iterator = markers.iterator();
        while (iterator.hasNext()) {
            T next = iterator.next();
            double distance = CommonMapUtils.getDistance(last.getLatitude(), last.getLongitude(), next.getLatitude(), next.getLongitude());
            if (distance > tolerance) {
                // 如果距离大于容忍距离，则保留当前点，并更新最后一个点
                resultMarkers.add(next);
                last = next;
            }
            iterator.remove();
        }
        return resultMarkers;
    }



}
